#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2022/03/02
# @Author   :Changshu
# @File     :Exercise4.py
# 4. 寻找两个正序数组的中位数


def test1(nums1: list, nums2: list):
	nums = []
	m, n = len(nums1), len(nums2)
	i, j = 0, 0
	for count in range(m + n):
		n1, n2 = 10 ** 7, 10 ** 7
		if i < m:
			n1 = nums1[i]
		if j < n:
			n2 = nums2[j]
		if n1 <= n2:
			nums.append(n1)
			i += 1
		else:
			nums.append(n2)
			j += 1
	return nums

def findMedianSortedArrays2(self, nums1: list, nums2: list) -> float:
	nums=[]
	m,n=len(nums1),len(nums2)
	i,j=0,0
	for count in range(m+n):
		n1,n2=10**7,10**7
		if i<m:
			n1=nums1[i]
		if j<n:
			n2=nums2[j]
		if n1<=n2:
			nums.append(n1)
			i+=1
		else:
			nums.append(n2)
			j+=1
		if (m+n)%2==0:
			return (nums[((m+n)//2)-1]+nums[((m+n)//2)])/2
		else:
			return nums[((m+n)//2)]


def findMedianSortedArrays(nums1: list, nums2: list) -> float:
	m,n=len(nums1),len(nums2)
	left,right=-1,-1
	aStart,bStart=0,0
	for i in range((m+n)//2+1):
		left=right
		if aStart<m and (bStart>=n or nums1[aStart]<nums2[bStart]):
			right=nums1[aStart]
			aStart+=1
		else:
			right=nums2[bStart]
			bStart+=1
	if (m+n)%2==0:
		return (left+right)/2
	return right

if __name__ == '__main__':
	# num1=[1,3,4,9]
	# num2=[1,2,3,4,5,6,7,8,9,10]
	# print(test1(num1,num2))
	# for i in range(2,5):
	# 	print(i)
	num1 = [1, 3]
	num2 = [2]
	print(findMedianSortedArrays(num1,num2))